一、VR-GCN [2017]

《Stochastic Training of Graph Convolutional Networks with Variance Reduction》

1. 图卷积网络（graph convolution network: GCN ）将卷积神经网络CNN 推广到图结构化数据。图卷积（graph convolution）操作对节点的所有邻居应用相同的线性变换，然后是均值池化和非线性激活函数。通过堆叠多个图卷积层，GCN 可以利用来自遥远邻居的信息来学习 node representation 。GCN 及其变体已被应用于半监督节点分类、inductive node embedding 、链接预测、 以及知识图谱，超越了不使用图结构的多层感知机 MLP 以及不使用节点特征的 graph embedding 方法。

   然而，图卷积操作使得 GCN 难以高效地训练。考虑一个 $L$$L$ 层的图卷积神经网络GCN，节点的第 $l$$l$ 层的 hidden feature 需要递归地通过其邻域内所有节点的第 $l-1$$l-1$ 层 hidden feature 来计算。因此，如下图 (a) 所示，单个节点的感受野（receptive field） 的大小随网络层数呈指数型增长。

   • 为解决感受野太大的问题，《Semi-supervised classification with graph convolutional networks》 提出通过 batch 算法来训练 GCN，该方法同时计算 batch 内所有节点的 representation。但是，由于 batch 算法收敛速度慢，以及需要将整个数据集放入到 GPU 中，因此无法处理大规模数据集。

   • 《Inductive representation learning on large graphs》 尝试邻域采样（ neighbor sampling: NS） 的方法为GCN 提出随机训练算法。在 NS 算法中，他们并未考虑节点的所有邻居，而是为每个节点在第 $l$$l$ 层随机采样 $D^{(l)}$$D^{(l)}$ 个邻居，如图 (b) 所示。这可以将感受野的大小减小到 $\prod _l{D}^{(l)}$$\prod_l D^{(l)}$ 。他们发现对于两层的 GCN 网络，选择 $D^{(1)}=10,D^{(2)}=25$$D^{(1)}=10, D^{(2)} = 25$ 可以实现与原始 GCN 相当的性能。

   理论上当 $D^{(l)}=1$$D^{(l)} = 1$ 时（即每个节点的预测仅依靠它本身，不依赖任何其它邻域节点）计算效率最高，此时模型退化为基于节点的多层感知机 MLP 。虽然 Hamilton 的方法复杂度降低，但是仍然比 MLP 要大 $D^{(1)}\times D^{(2)}=250$$D^{(1)}\times D^{(2)} = 250$ 倍，仍然无法让人满意。

   另外，使用基于邻域采样的随机训练算法能否确保模型收敛，尚无理论上的保证。

   在论文 《Stochastic Training of Graph Convolutional Networks with Variance Reduction》 中，作者为 GCN 设计了新颖的基于控制变量的（ control variate-based ）随机逼近算法，即 GCN with Variance Reduction: VRGCN 。

   VRGCN 利用节点的历史激活值（即历史hidden feature）作为控制变量（control variate）。作者表明：通过邻域采样NS 策略得到的 hidden feature 的方差取决于 hidden feature 的幅度（magnitude）（因为 hidden feature 是一个向量），而VRGCN 得到的 hidden feature 的方差取决于 hidden feature 和它历史均值之间的差异（ difference）。

   另外，VRGCN 还带来了理论上的收敛性保证。VRGCN 可以给出无偏的（相比较于原始的 GCN）、零方差的预测。并且训练算法可以收敛到GCN 损失函数的局部最优值，而与采样大小 $D^{(l)}$$D^{(l)}$ 无关。理论分析表明：VRGCN 可以通过仅对节点采样两个邻居节点来显著降低模型的时间复杂度，同时保持模型的质量。

   作者在六个 graph 数据集上对 VRGCN 进行了实验测试，并表明 VRGCN 显著降低了具有相同感受野大小的 NS 的梯度的偏差（bias）和方差（variance）。尽管仅采样 $D^{(l)}=2$$D^{(l)} = 2$ 个邻居，但是 VRGCN 在所有数据集上的可比数量的 epoch 中实现了与精确算法相同的预测性能，即，VRGCN 降低了时间复杂度同时几乎没有损失收敛速度，这是我们可以预期的最好结果。在最大的 Reddit 数据集上，VRGCN 算法的训练时间相比精确算法（《Semi-supervised classification with graph convolutional networks》）、邻域采样算法（《Inductive representation learning on large graphs》）、重要性采样算法（《Fastgcn: Fast learning with graph convolutional networks via importance sampling》）要少 7 倍。

   

1.1 模型

1.1.1 GCN

1. 我们以半监督节点分类任务的 GCN 作为说明，当然我们的算法不局限于任务类型，也不局限于模型类型。我们的算法适用于任何涉及到计算邻居平均激活值的其它模型，以及其它任务。

2. 给定图 $G=(\mathcal{V},\mathcal{E})$$G=(\mathcal V,\mathcal E)$ ，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为节点集合， $\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为所有边集合， 边 $e_{i,j}=(v_i,v_j)$$e_{i,j} = (v_i,v_j)$ 为无向边。

   每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ ，以及一个label $y_v$$y_v$ 。在半监督学习场景中，我们只能观测到部分节点的 label，这部分节点的集合记作 ${\mathcal{V}}_Y$$\mathcal V_Y$ 。我们的目标是预测剩余节点集合 ${\mathcal{V}}_U=\mathcal{V}-{\mathcal{V}}_Y$$\mathcal V_U = \mathcal V- \mathcal V_Y$ 中每个节点的 label 。

3. 定义邻接矩阵 $\mathbf{A}\in {\mathbb{R}}^{|\mathcal{V}|\times |\mathcal{V}|}$$\mathbf A\in \mathbb R^{|\mathcal V|\times |\mathcal V|}$ ，其中 $A_{i,j}$$A_{i,j}$ 表示节点 $v_i,v_j$$v_i,v_j$ 之间的链接权重，如果 $v_i,v_j$$v_i,v_j$ 之间不存在链接则 $A_{i,j}=0$$A_{i,j} = 0$ 。由于是无向图因此 $\mathbf{A}$$\mathbf A$ 是对称矩阵。

   定义传播矩阵 propagation matrix $\mathbf{P}\in {\mathbb{R}}^{|\mathcal{V}|\times |\mathcal{V}|}$$\mathbf P\in \mathbb R^{|\mathcal V|\times |\mathcal V|}$ 为归一化的邻接矩阵：

   $$\begin{array}{c}\tilde{\mathbf{A}}=\mathbf{I}+\mathbf{A}\\ \tilde{\mathbf{D}}=\text{diag}({\tilde{D}}_{i,i}),{\tilde{D}}_{i,i}=\sum _j{\tilde{A}}_{i,j}\\ \mathbf{P}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\end{array}$$

   其中 $\tilde{\mathbf{A}}$$\tilde{\mathbf A}$ 为添加了 self-loop 的邻接矩阵。

   因此一个图卷积层可以定义为（假设当前为第 $l+1$$l+1$ 层）：

   $$\begin{array}{c}{\mathbf{Z}}^{(l+1)}=\mathbf{P}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\\ {\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{Z}}^{(l+1)}\right)\end{array}$$

   其中：

   • ${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ 为第 $l$$l$ 层的hidden feature 矩阵，也称作激活矩阵（ activataion matrix）。

     第 $v$$v$ 行 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 表示节点 $v$$v$ 的 hidden feature 向量，也称作激活值（ activation）。

   • ${\mathbf{H}}^{(0)}=\mathbf{X}$$\mathbf H^{(0)} = \mathbf X$ 为输入的特征矩阵，第 $v$$v$ 行 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ 表示节点 $v$$v$ 的特征向量。

   • ${\mathbf{W}}^{(l)}$$\mathbf W^{(l)}$ 为第 $l+1$$l+1$ 层模型待学习的权重矩阵，它在所有节点上共享。

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。

   假设 GCN 模型有 $L$$L$ 层，则GCN 模型的训练损失函数为：

   $$\mathcal{J}=\frac{1}{|{\mathcal{V}}_Y|}\sum _{v\in {\mathcal{V}}_Y}f(y_v,{\overrightarrow{\mathbf{z}}}_v^{(L)})$$

   其中：

   • $f(\cdot ,\cdot )$$f(\cdot,\cdot)$ 为单个节点的损失函数。

   • ${\overrightarrow{\mathbf{z}}}_v^{(L)}$$\mathbf{\vec z}_v^{(L)}$ 为 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 的第 $v$$v$ 行，表示节点 $v$$v$ 的 final representation。

4. 卷积层通过 $\mathbf{P}{\mathbf{H}}^{(l)}$$\mathbf P\mathbf H^{(l)}$ 计算邻域均值，从而将邻域信息传递到当前节点。定义节点 $v$$v$ 的邻域集合为 ${\mathcal{N}}_v$$\mathcal N_v$ ，则节点 $v$$v$ 的邻域均值 hidden feature 向量为：

   $${\overrightarrow{\mathbf{n}}}_v^{(l)}=\sum _{u=1}^{\mathcal{V}}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}$$

   它就是 $\mathbf{P}{\mathbf{H}}^{(l)}$$\mathbf P \mathbf H^{(l)}$ 的第 $v$$v$ 行，等于邻域hidden feature 的加权和。

   定义节点 $v$$v$ 在第 $l$$l$ 层的感受野（ receptive field ）为：为计算 ${\overrightarrow{\mathbf{z}}}_v^{(L)}$$\mathbf{\vec z}_v^{(L)}$ 所需要的 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 的节点集合。

   • 对于一个 $L$$L$ 层的 GCN，节点 $v$$v$ 的所有感受野就是它的 L-hop 邻域集合。

   • 当 $\mathbf{P}=\mathbf{I}$$\mathbf P = \mathbf I$ 时，GCN 退化为一个多层感知机 MLP，其中不涉及任何图结构信息。对于多层感知机，节点 $v$$v$ 的感受野就是它本身 $\{v\}$$\{v\}$ 。

5. GCN 训练损失函数的 batch 梯度为：

   $$\mathrm{\nabla }\mathcal{J}=\frac{1}{|{\mathcal{V}}_Y|}\sum _{v\in {\mathcal{V}}_Y}\mathrm{\nabla }f(y_v,{\overrightarrow{\mathbf{z}}}_v^{(L)})$$

   由于每次迭代都涉及整个标记节点集合 ${\mathcal{V}}_Y$$\mathcal V_Y$ ，因此计算 batch 梯度代价太大。

   一个可行的方案是采用随机梯度作为 batch 梯度的近似值：

   $$\mathrm{\nabla }\mathcal{J}\simeq \frac{1}{|{\mathcal{V}}_B|}\sum _{v\in {\mathcal{V}}_B}\mathrm{\nabla }f(y_v,{\overrightarrow{\mathbf{z}}}_v^{(L)})$$

   其中 ${\mathcal{V}}_B\subset {\mathcal{V}}_Y$$\mathcal V_B\sub \mathcal V_Y$ 为标记节点集合的一个 mini-batch 。

   但是，由于感受野太大，mini-batch 梯度的计算代价仍然很高。例如，NELL 数据集的 2-hop 邻域平均包含 1597 个节点，这意味着在一个 2 层 GCN 中，为计算单个节点的梯度需要涉及 1597/65755 = 2.4% 的全部节点。

1.1.2 GraphSAGE

1. 为降低感受野大小，GraphSAGE 提出了邻域采样（neighbor sampling: NS）策略。 在第 $l$$l$ 层，对于每个节点 NS 策略随机采样 $D^{(l)}$$D^{(l)}$ 个邻居，并基于蒙特卡洛近似来给出节点 $v$$v$ 的邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 的一个近似估计 ${\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}$$\mathbf{\vec n}_{NS,v}^{(l)}$ ：

   $${\overrightarrow{\mathbf{n}}}_v^{(l)}\simeq {\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}=\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}$$

   其中 ${\hat{\mathcal{N}}}_v^{(l)}\subset {\mathcal{N}}_v$$\hat{\mathcal N}_v^{(l)}\sub \mathcal N_v$ 为一个大小为 $D^{(l)}$$D^{(l)}$ 的、邻域 ${\mathcal{N}}_v$$\mathcal N_v$ 的一个随机子集。

   因此 NS 策略降低了感受野大小，从 L-hop 邻域大小降低到采样后的邻域大小 $\prod _{l=1}^L{D}^{(l)}$$\prod_{l=1}^L D^{(l)}$ 。

   我们将 ${\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}$$\mathbf{\vec n}_{NS,v}^{(l)}$ 称作 ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 的 NS 估计量，而 ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 为精确值。

   上述邻域采样策略以矩阵的形式可以重写为：

   $$\begin{array}{c}{\mathbf{Z}}^{(l+1)}={\hat{\mathbf{P}}}^{(l)}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\\ {\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{Z}}^{(l+1)}\right)\end{array}$$

   其中传播矩阵 $\mathbf{P}$$\mathbf P$ 被替换为一个稀疏的、无偏的估计 ${\hat{\mathbf{P}}}^{(l)}$$\hat{\mathbf P}^{(l)}$ ，即满足 ： $\mathbb{E}\left[{\hat{\mathbf{P}}}^{(l)}\right]=\mathbf{P}$$\mathbb E\left[\hat{\mathbf P}^{(l)}\right ] = \mathbf P$ 。采样后的传播矩阵 ${\hat{\mathbf{P}}}^{(l)}$$\hat{\mathbf P}^{(l)}$ 为：

   $$\begin{array}{c}{\hat{P}}_{v,u}^{(l)}=\{\begin{array}{ll}\frac{|{\mathcal{N}}_v|}{D^{(l)}}{P}_{v,u}& ,u\in {\hat{\mathcal{N}}}_v^{(l)}\\ 0& ,\text{else}\end{array}\end{array}$$

2. 在 GraphSAGE 的随机梯度下降过程中，存在两个随机性来源：

   • 选择 mini-batch ${\mathcal{V}}_B\subset {\mathcal{V}}_Y$$\mathcal V_B\sub \mathcal V_Y$ 引入的随机性。

   • 选择大小为 $D^{(l)}$$D^{(l)}$ 的邻域集合 ${\hat{\mathcal{N}}}_v^{(l)}\subset {\mathcal{N}}_v$$\hat{\mathcal N}_v^{(l)}\sub \mathcal N_v$ 引入的随机性。

   尽管 ${\hat{\mathbf{P}}}^{(l)}$$\hat{\mathbf P}^{(l)}$ 是 $\mathbf{P}$$\mathbf P$ 的无偏估计，但是由于非线性函数 $\sigma (\cdot )$$\sigma(\cdot)$ 的存在， $\sigma \left({\hat{\mathbf{P}}}^{(l)}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$\sigma\left(\hat{\mathbf P}^{(l)}\mathbf H^{(l)} \mathbf W^{(l)}\right)$ 并不是 $\sigma \left({\mathbf{P}}^{(l)}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$\sigma\left(\mathbf P ^{(l)}\mathbf H^{(l)} \mathbf W^{(l)}\right)$ 的无偏估计。因此，在 NS 策略中节点的 final representaion 矩阵 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 以及梯度 $\mathrm{\nabla }f(y_v,{\overrightarrow{\mathbf{z}}}_v^{(L)})$$\nabla f\left(y_v,\mathbf{\vec z}_v^{(L)}\right)$ 都是有偏的。最终 NS 策略中随机梯度下降 SGD 的收敛性得不到保障，除非采样大小 $D^{(l)}$$D^{(l)}$ 趋向于无穷大。因为这时候计算的梯度 $\mathrm{\nabla }f(y_v,{\overrightarrow{\mathbf{z}}}_v^{(L)})$$\nabla f\left(y_v,\mathbf{\vec z}_v^{(L)}\right)$ 是有偏的，无法保证它是沿着梯度的正确方向。

3. 在 GraphSAGE 中，由于梯度是有偏的，因此 NS 策略中的采样大小 $D^{(l)}$$D^{(l)}$ 必须很大，从而确保模型得到和 exact 策略相近的预测性能。

   在 GraphSAGE 中Hamilton 选择 $D^{(1)}=10,D^{(2)}=25$$D^{(1)} = 10, D^{(2)} = 25$ ，因此感受野的大小为 $D^{(1)}\times D^{(2)}=250$$D^{(1)}\times D^{(2)} = 250$，这远大于 MLP 的感受野（大小为 1），因此训练仍然代价较高。

1.1.3 FastGCN

1. FastGCN 是另一种类似于NS 的基于采样的算法。FastGCN 并没有为每个节点采样邻域，而是直接采样每一层的、所有节点共享的感受野。

   对于第 $l$$l$ 层，FastGCN 首先采样 $D^{(l)}$$D^{(l)}$ 个样本的集合 ${\mathbb{S}}^{(l)}=\{v_1^{(l)},\cdots ,v_{D^{(l)}}^{(l)}\}$$\mathbb S^{(l)}=\left\{v_1^{(l)},\cdots,v_{ D^{(l) }}^{(l)}\right\}$ ，然后通过这 $D^{(l)}$$D^{(l)}$ 个样本来计算每个节点 $v$$v$ 的邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ ：

   $${\overrightarrow{\mathbf{n}}}_v^{(l)}=\sum _{u=1}^{\mathcal{V}}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}\simeq \frac{|\mathcal{V}|}{D^{(l)}}\sum _{u\in \mathbb{S}}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}/q(u)$$

   其中重要性分布：

   $$q(u)\propto \sum _{v=1}^{|\mathcal{V}|}{P}_{u,v}^2$$

   我们将这种邻域均值 hidden feature 的估计称作重要性采样（importance sampling: IS）。

   • 注意，IS 采样策略和 NS 采样策略的区别在于：前者为第 $l$$l$ 层所有节点采样 $D^{(l)}$$D^{(l)}$ 个节点，后者为第 $l$$l$ 层每个节点分别采样 $D^{(l)}$$D^{(l)}$ 个节点。

   • 当 $D^{(l)}$$D^{(l)}$ 较大且选择 $q(u)\propto \sum _{(u,v)\in \mathcal{E}}\frac{1}{|{\mathcal{N}}_v|}$$q(u)\propto \sum_{(u,v)\in \mathcal E} \frac{1}{|\mathcal N_v|}$ 时，IS 可以视为 NS ，因为每个节点 $v$$v$ 以概率 $\frac{1}{|{\mathcal{N}}_v|}$$\frac{1}{|\mathcal N_v|}$ 来选择其邻居节点 $u$$u$ 。因此 NS 可以看作是 IS 的一种。

2. 尽管 IS 策略的感受野大小为 $\sum _l{D}^{(l)}$$\sum_l D^{(l)}$ 要小于 NS 策略的感受野大小 $\prod _l{D}^{(l)}$$\prod_l D^{(l)}$ ，但是 IS 仍然仅在采样大小 $D^{(l)}$$D^{(l)}$ 达到无穷大时才可以确保模型收敛。

   从实验来看，我们发现 IS 策略的效果要比 NS 更差，这是因为：在 IS 策略中我们为所有节点采样了共同的一组节点集合，对于部分节点我们采样到了它们的很多个邻居，对于另一些节点我们没有采样到任何邻居。对于后者，这些节点的邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 为零，从而导致 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 为零 。

1.1.4 控制变量

1. 我们提出一种新的基于控制变量（control variate: CV）的算法，该算法基于历史 hidden feature 来降低估计量的方差。

2. 当计算邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec n}_v^{(l)} = \sum_{u\in \mathcal N_v} P_{v,u} \mathbf{\vec h}_u^{(l)}$ 时，由于需要递归计算，因此我们无法计算所有的 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 项 。我们的思想是：对于每个 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ ，我们维护一份历史均值 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 作为其计算代价负担得起（affordable）的近似值。每次计算 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 时，我们都用 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 去更新 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 。当训练期间模型的权重变化比较缓慢时，我们预期 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 和 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 是近似的。

   令 $\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}={\overrightarrow{\mathbf{h}}}_u^{(l)}-{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\Delta \mathbf{\vec h}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \bar{\mathbf{\vec h}}_u^{(l)}$ ，则有：

   $${\overrightarrow{\mathbf{n}}}_v^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}+\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$

   定义：

   $${\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}=\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}+\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$

   其中 ${\hat{\mathcal{N}}}_v^{(l)}\subset {\mathcal{N}}_v$$\hat{\mathcal N}_v^{(l)}\sub \mathcal N_v$ 为一个大小为 $D^{(l)}$$D^{(l)}$ 的、邻域 ${\mathcal{N}}_v$$\mathcal N_v$ 的一个随机子集。

   这里的核心思想是：主要的 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 不用递归计算，可以直接从内存中获取到；次要的 $\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}$$\Delta \mathbf{\vec h}_u^{(l)}$ 需要递归计算，但是仅对它采样一小部分的邻域。同时，这进一步促进了模型权重的缓慢变化。

   因为主要部分是精确值，次要部分是近似值，因此这会大幅度降低近似计算带来的影响。

   则有：${\overrightarrow{\mathbf{n}}}_v^{(l)}\simeq {\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}$$\mathbf{\vec n}_{ v}^{(l)} \simeq \mathbf{\vec n}_{CV,v}^{(l)}$ 。我们称 ${\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}$$\mathbf{\vec n}_{CV,v}^{(l)}$ 为节点的邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 的 CV 估计量。写作矩阵的形式为：

   $$\begin{array}{c}{\mathbf{Z}}^{(l+1)}=({\hat{\mathbf{P}}}^{(l)}({\mathbf{H}}^{(l)}-{\overline{\mathbf{H}}}^{(l)})+\mathbf{P}{\overline{\mathbf{H}}}^{(l)}){\mathbf{W}}^{(l)}\\ {\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{Z}}^{(l+1)}\right)\end{array}$$

   其中 ${\overline{\mathbf{H}}}^{(l)}$$\bar{\mathbf H}^{(l)}$ 的各行为 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 拼接而成 。

   这里我们仅对 $\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}$$\Delta{\mathbf{\vec h}}_u^{(l)}$ 的项进行蒙特卡洛近似。对所有的 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 取平均是可以接受的，因为它们不需要进行递归地计算。

   由于我们预期 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 和 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 是近似的，因此 $\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u$$\Delta \mathbf{\vec h}_u$ 很小。因此 ${\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}$$\mathbf{\vec n}_{CV,v}^{(l)}$ 具有比 ${\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}$$\mathbf{\vec n}_{NS,v}^{(l)}$ 更小的方差。具体而言，如果模型的权重保持固定，则 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 应该最终等于 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ ，因此有：

   $${\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}=0+\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}={\overrightarrow{\mathbf{n}}}_v^{(l)}$$

   即估计量的偏差和方差都为零。

3. 我们定义控制变量（control variate）为：

   $${\overrightarrow{\delta }}_v^{(l)}={\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}-{\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}-\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$

   我们将控制变量 ${\overrightarrow{\delta }}_v^{(l)}$$\vec \delta_v^{(l)}$ 添加到邻域采样策略 NS 的 ${\overrightarrow{\mathbf{n}}}_{NS,v}^{(l)}$$\mathbf{\vec n}_{NS,v}^{(l)}$ 中，从而降低估计量的方差。

   现在 ${\overrightarrow{\delta }}_v^{(l)}$$\vec \delta_v^{(l)}$ 仅依赖于不需要递归计算的 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$，因此 ${\overrightarrow{\delta }}_v^{(l)}$$\vec \delta_v^{(l)}$ 也不需要递归计算。

4. 采用 CV 估计量来训练 GCN 的方法和 NS 估计量都相同。具体而言，在 GCN 的每轮迭代中都执行以下算法。

   VRGCN 迭代算法：

   • 随机选择一个 mini-batch 的节点 ${\mathcal{V}}_B\subset {\mathcal{V}}_Y$$\mathcal V_B\sub \mathcal V_Y$ 。

   • 构建一个计算图，其中包含当前 mini-batch 每个节点的 hidden feature 计算时需要的其它节点的 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 及其历史均值 ${\overline{\overrightarrow{\mathbf{h}}}}_v^{(l)}$$\bar{\mathbf{\vec h}}_v^{(l)}$ 。

   • 根据下面的前向传播公式进行传播：

     $$\begin{array}{c}{\mathbf{Z}}^{(l+1)}=({\hat{\mathbf{P}}}^{(l)}({\mathbf{H}}^{(l)}-{\overline{\mathbf{H}}}^{(l)})+\mathbf{P}{\overline{\mathbf{H}}}^{(l)}){\mathbf{W}}^{(l)}\\ {\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{Z}}^{(l+1)}\right)\end{array}$$

     这里控制变量 ${\overrightarrow{\delta }}_v^{(l)}$$\vec \delta_v^{(l)}$ 的矩阵形式为：$\mathbf{P}{\overline{\mathbf{H}}}^{(l)}-{\hat{\mathbf{P}}}^{(l)}{\overline{\mathbf{H}}}^{(l)}$$\mathbf P\bar{\mathbf H}^{(l)} - \hat{\mathbf P}^{(l)}\bar{\mathbf H}^{(l)}$ 。

   • 通过反向传播计算梯度，并更新参数。

   • 更新 hidden feature 历史均值 ${\overline{\overrightarrow{\mathbf{h}}}}_v^{(l)}$$\bar{\mathbf{\vec h}}_v^{(l)}$ 。

   其中，第二步的计算图是通过每层的感受野 ${\mathcal{R}}^{(l)}$$\mathcal R^{(l)}$ 以及对应的传播矩阵 ${\hat{\mathbf{P}}}^{(l)}$$\hat {\mathbf P}^{(l)}$ 来定义。感受野 ${\mathcal{R}}^{(l)}$$\mathcal R^{(l)}$ 定义了需要第 $l$$l$ 层哪些节点的 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 来计算当前的 mini-batch 。

   我们自顶向下构建 ${\mathcal{R}}^{(l)}$$\mathcal R^{(l)}$ 以及 ${\hat{\mathbf{P}}}^{(l)}$$\hat {\mathbf P}^{(l)}$ ：

   • 令 ${\mathcal{R}}^{(L)}={\mathcal{V}}_B$$\mathcal R^{(L)} = \mathcal V_B$ 。

   • 对于第 $l$$l$ 层，对 ${\mathcal{R}}^{(l+1)}$$\mathcal R^{(l+1)}$ 中的每个节点我们都从它们的邻域中各自随机选择 $D^{(l)}$$D^{(l)}$ 个邻居节点并加入到 ${\mathcal{R}}^{(l)}$$\mathcal R^{(l)}$ 中。

     注意：我们假设 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 永远都必须参与 ${\overrightarrow{\mathbf{h}}}_v^{(l+1)}$$\mathbf{\vec h}_v^{(l+1)}$ 的计算，即 $v$$v$ 每次都作为其自己的邻居一定被选中。

   VRGCN 的感受野如下图 (c) 所示，其中红色节点为感受野，其 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 来计算当前的 mini-batch 。蓝色节点的历史 hidden feature 均值 ${\overline{\overrightarrow{\mathbf{h}}}}_v^{(l)}$$\bar{\mathbf{\vec h}}_v^{(l)}$ 也用于计算当前的 mini-batch 。

   

1.1.5 理论分析

1. 为便于理论分析估计量的方差，这里我们假设所有的特征都是一维的。通过分别处理每个维度，我们的分析结论可以推广到多维。

2. 假设 ${\hat{\mathcal{N}}}_v^{(l)}$$\hat{\mathcal N}^{(l)}_v$ 通过从 ${\mathcal{N}}_v$$\mathcal N_v$ 进行无放回采样 $D^{(l)}$$D^{(l)}$ 个样本得到，则我们有结论：

   $${\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}\left[\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{x}_u\right]=\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}(x_{u_1}-x_{u_2}{)}^2$$

   其中 $C_v^{(l)}=1-(D^{(l)}-1)/(|{\mathcal{N}}_v|-1)$$C_v^{(l)} = 1-(D^{(l)}-1)/(|\mathcal N_v| - 1)$ 。 证明见原始论文的附录。

   根据以上结论，对于 NS 估计量我们有：

   $${\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}\left[n_{NS,v}^{(l)}\right]=\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}{(P_{v,u_1}{h}_{u_1}^{(l)}-P_{v,u_2}{h}_{u_2}^{(l)})}^2$$

   即邻域内所有邻居pair 对的加权 hidden feature 之间的距离之和。如果邻域内所有节点的 $P_{v,u}{h}_u$$P_{v,u}h_u$ 都相等，则该方差为零。此时，任何邻域节点都包含了整个邻域的信息。

   同样地，对于 CV 估计量我们有：

   $${\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}\left[n_{CV,v}^{(l)}\right]=\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}{(P_{v,u_1}\mathrm{\Delta }{h}_{u_1}^{(l)}-P_{v,u_2}\mathrm{\Delta }{h}_{u_2}^{(l)})}^2$$

   相比较于 NS 估计量，这里仅需要将 $h_u^{(l)}$$h_u^{(l)}$ 替代为 $\mathrm{\Delta }{h}_u^{(l)}$$\Delta h_u^{(l)}$ 。由于 $\mathrm{\Delta }{h}_u^{(l)}$$\Delta h_u^{(l)}$ 通常都比 $h_u^{(l)}$$h_u^{(l)}$ 更小，因此 CV 估计量通常都比 NS 估计量的方差更小。

   进一步地，正如我们在下文中分析到的，由于训练期间 间 $\mathrm{\Delta }{h}_u^{(l)}$$\Delta h_u^{(l)}$ 收敛到零，因此我们不仅降低了方差，甚至消除了方差。

3. 除了较小的方差，CV 估计量比 NS 估计量还具有更强的理论收敛性保证。这里我们提出两个定理：

   • 如果模型参数固定，则在 inference 期间，CV 会在 $L$$L$ （ $L$$L$ 为卷积层的层数）个 epoch 之后产生 exact 预测。

   • 无论邻域采样大小如何，模型都会朝着局部最优解收敛。

4. 假设算法执行多个 epoch，在每个 epoch 中我们将节点集合 $\mathcal{V}$$\mathcal V$ 划分为 $I$$I$ 个 mini-batch：$\{{\mathcal{V}}_1,\cdots ,{\mathcal{V}}_I\}$$\{\mathcal V_1,\cdots,\mathcal V_I\}$ 。在第 $i$$i$ 个迭代步，我们对 mini-batch ${\mathcal{V}}_i$$\mathcal V_i$ 中的节点进行前向传播和反向传播，从而更新模型参数以及节点的历史 hidden feature 均值。

   注意：在每个 epoch 中我们扫描所有节点，而不仅仅是标记的训练节点，从而确保每个 epoch 中对每个节点的历史 hidden feature 均值至少进行了一次更新。

   记第 $i$$i$ 次迭代中模型的参数为 ${\mathbf{W}}_i$$\mathbf W_i$ 。在训练期间 ${\mathbf{W}}_i$$\mathbf W_i$ 通过 SGD 随时间更新，在测试期间 $\mathbf{W}={\mathbf{W}}_T$$\mathbf W = \mathbf W_T$ 被固化下来，其中 $T$$T$ 为迭代的总次数。

   记第 $i$$i$ 次迭代的 exact hidden feature 为 ${\mathbf{H}}_i^{(l)}$$\mathbf H ^{(l)}_i$ ，以及对应的 $\mathbf{Z}$$\mathbf Z$ 为 ${\mathbf{Z}}_i^{(l)}$$\mathbf Z_i ^{(l)}$ ；使用 CV 估计量的 hidden feature 为 ${\mathbf{H}}_{CV,i}^{(l)}$$\mathbf H_{CV,i}^{(l)}$ ，以及对应的 $\mathbf{Z}$$\mathbf Z$ 为 ${\mathbf{Z}}_{CV,i}^{(l)}$$\mathbf Z_{CV,i}^{(l)}$ 。

   在第 $i$$i$ 轮迭代，网络计算 mini-batch ${\mathcal{V}}_i$$\mathcal V_i$ 的损失函数和梯度，其中：

   • 对于 exact 算法，其损失函数和梯度分别为：

     $$\begin{array}{c}J({\mathbf{W}}_i)=\frac{1}{|{\mathcal{V}}_i|}\sum _{v\in {\mathcal{V}}_i}f(y_v,{\overrightarrow{\mathbf{z}}}_{i,v}^{(L)})\\ {\mathbf{G}}_i({\mathbf{W}}_i)=\mathrm{\nabla }{\mathcal{J}}_{\mathbf{W}}\simeq \frac{1}{|{\mathcal{V}}_i|}\sum _{v\in {\mathcal{V}}_i}{\mathrm{\nabla }}_{{\mathbf{W}}_i}f(y_v,{\overrightarrow{\mathbf{z}}}_{i,v}^{(L)})\end{array}$$

     对于 exact 算法，如果 ${\mathbf{W}}_i$$\mathbf W_i$ 是 constant 序列，则可以忽略下标 $i$$i$ 。

   • 对于 CV 算法，其损失函数和梯度分别为：

     $$\begin{array}{c}{J}_{CV}({\mathbf{W}}_i)=\frac{1}{|{\mathcal{V}}_i|}\sum _{v\in {\mathcal{V}}_i}f(y_v,{\overrightarrow{\mathbf{z}}}_{i,CV,v}^{(L)})\\ {\mathbf{G}}_{i,CV}({\mathbf{W}}_i)=\mathrm{\nabla }{\mathcal{J}}_{CV,\mathbf{W}}\simeq \frac{1}{|{\mathcal{V}}_i|}\sum _{v\in {\mathcal{V}}_i}{\mathrm{\nabla }}_{{\mathbf{W}}_i}f(y_v,{\overrightarrow{\mathbf{z}}}_{i,CV,v}^{(L)})\end{array}$$

     梯度 ${\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$\mathbf G_{i,CV} (\mathbf W_i)$ 有两个随机性来源：

     • 选择 mini-batch ${\mathcal{V}}_i\subset {\mathcal{V}}_Y$$\mathcal V_i\sub \mathcal V_Y$ 引入的随机性。

     • 选择大小为 $D^{(l)}$$D^{(l)}$ 的邻域集合 ${\hat{\mathcal{N}}}_v^{(l)}\subset {\mathcal{N}}_v$$\hat{\mathcal N}_v^{(l)}\sub \mathcal N_v$ 引入的随机性（由采样后的邻接矩阵 $\hat{\mathbf{P}}$$\hat{\mathbf P}$ 来刻画） 。

     因此我们考虑 ${\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$\mathbf G_{i,CV} (\mathbf W_i)$ 对 ${\mathcal{V}}_i$$\mathcal V_i$ 的期望、或者对 $\hat{\mathbf{P}}$$\hat{\mathbf P}$ 的期望、或者对二者的共同期望。

5. 以下定理解释了 CV 的近似预测和 exact 预测之间的关系：

   对于一个 constant sequence ${\mathbf{W}}_i=\mathbf{W}$$\mathbf W_i = \mathbf W$ ，以及任意 $i>L\times I$$i\gt L\times I$ （即 $L$$L$ 个 epoch 之后），通过 CV 估计量计算的 hidden feature 和 exact 计算的相等。即：

   $$\begin{array}{c}{\mathbf{H}}_{i,CV}^{(l)}={\mathbf{H}}_i^{(l)},1\le l\le L\\ {\mathbf{Z}}_{i,CV}^{(l)}={\mathbf{Z}}_i^{(l)},1\le l\le L\end{array}$$

   其证明见原始论文附录。

   该定理表明：在 inference 期间，我们可以使用 CV 估计量进行前向传播 $L$$L$ 个 epoch （通常 $L$$L$ 很小，比如两层的 GCN 网络中 $L=2$$L=2$ ），然后得到 exact 预测。这优于 NS 估计量，因为除非邻域大小无穷大，否则 NS 估计量无法恢复 exact 预测。

   和直接进行 exact 预测的 batch 算法相比，CV 估计量可扩展性更强，因为它不需要将整个图加载到内存中。

6. 以下定理表明，无论邻域采样大小 $D^{(l)}$$D^{(l)}$ 如何，采用近似梯度 ${\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$\mathbf G_{i,CV} (\mathbf W_i)$ 的 SGD 训练仍然收敛于局部最优。因此我们可以选择任意小的 $D^{(l)}$$D^{(l)}$ 而不必担心收敛性。

   定理：假设：

   • 激活函数 $\sigma (\cdot )$$\sigma(\cdot)$ 为 $\rho -\text{Lipschitz}$$\rho-\text{Lipschitz}$ 。

   • 损失函数的梯度 ${\mathrm{\nabla }}_{\overrightarrow{\mathbf{z}}}f(y,\overrightarrow{\mathbf{z}})$$\nabla_{\mathbf{\vec z}}f(y,\mathbf{\vec z})$ 是 $\rho -\text{Lipschitz}$$\rho-\text{Lipschitz}$ 且有界的。

   • 对于任意的采样 $\hat{\mathbf{P}}$$\hat{\mathbf P}$ 、任意的节点子集 $\tilde{\mathcal{V}}$$\tilde{\mathcal V}$ 、任意的权重矩阵，都有 $||\mathbf{G}(\mathbf{W})|{|}_{\mathrm{\infty }},||{\mathbf{G}}_{\tilde{\mathcal{V}},CV}(\mathbf{W})|{|}_{\mathrm{\infty }},||{\mathrm{\nabla }}_{\mathbf{W}}\mathcal{J}(\mathbf{W})|{|}_{\mathrm{\infty }}$$||\mathbf G (\mathbf W) ||_\infty, || \mathbf G_{\tilde{\mathcal V},CV} (\mathbf W )||_\infty, ||\nabla_{\mathbf W} \mathcal J(\mathbf W)||_\infty$ 都是有界的，且上界都是 $G$$G$ （其中 $G>0$$G\gt 0$） 。

   • 损失函数 $\mathcal{J}(\mathbf{W})$$\mathcal J(\mathbf W)$ 是 $\rho -\text{smooth}$$\rho-\text{smooth}$ 的，即：对于任意 ${\mathbf{W}}_1,{\mathbf{W}}_2$$\mathbf W_1, \mathbf W_2$ ，有：

     $$|\mathcal{J}({\mathbf{W}}_2)-\mathcal{J}({\mathbf{W}}_1)-<\mathrm{\nabla }\mathcal{J}({\mathbf{W}}_1),{\mathbf{W}}_2-{\mathbf{W}}_1>|\le \frac{\rho }{2}||{\mathbf{W}}_2-{\mathbf{W}}_1|{|}_F^2$$

     其中 $<\mathbf{A},\mathbf{B}>=\text{tr}\left({\mathbf{A}}^{\mathrm{\top }}\mathbf{B}\right)$$<\mathbf A,\mathbf B> = \text{tr}\left(\mathbf A^\top \mathbf B\right)$ 为矩阵 $\mathbf{A}$$\mathbf A$ 和 $\mathbf{B}$$\mathbf B$ 的内积。

   则存在 $K>0$$K\gt 0$ ，使得 $\mathrm{\forall }N>L\times I$$\forall N\gt L\times I$ ，当我们执行 $1\le R\le N$$1\le R\le N$ 次 SGD 迭代时，有：

   $${\mathbb{E}}_R||\mathrm{\nabla }\mathcal{J}({\mathbf{W}}_R)|{|}_F^2\le 2\frac{\mathcal{J}({\mathbf{W}}_1)-\mathcal{J}({\mathbf{W}}^{\ast })+K+\rho K}{\sqrt{N}}$$

   其中：

   • $R$$R$ 为 [1, N] 之间均匀随机分布的变量。

   • 每次迭代都使用 CV 的近似梯度 ${\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$\mathbf G_{i,CV} (\mathbf W_i)$ ：

     $${\mathbf{W}}_{i+1}={\mathbf{W}}_i-\gamma \times {\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$

     其中步长 $\gamma =min\{\frac{1}{\rho },\frac{1}{\sqrt{N}}\}$$\gamma = \min\{\frac{1}{\rho}, \frac{1}{\sqrt N}\}$ 。

   从定理中我们看到：$\underset{N\to \mathrm{\infty }}{lim}{\mathbb{E}}_R||\mathrm{\nabla }\mathcal{J}({\mathbf{W}}_R)|{|}_F^2=0$$\lim_{N\rightarrow \infty} \mathbb E_R||\nabla \mathcal J(\mathbf W_R)||_F^2 = 0$ 。因此当迭代次数 $N$$N$ 趋向于无穷时，我们的训练算法收敛到局部最优解（梯度为零）。完整的证明见原始论文附录。

   简而言之，我们证明了近似梯度 ${\mathbf{G}}_{i,CV}({\mathbf{W}}_i)$$\mathbf G_{i,CV} (\mathbf W_i)$ 是 ${\mathbf{G}}_i({\mathbf{W}}_i)$$\mathbf G_{i} (\mathbf W_i)$ 的无偏估计，并且随着 $i\to \mathrm{\infty }$$i\rightarrow \infty$ 这种渐进无偏的 SGD 收敛到局部最优解。

1.1.6 dropout

1. 这里我们引入第三种随机性来源：对输入特征的随机 dropout 。

   令 ${\mathcal{D}}_p(\mathbf{X})=\mathbf{M}\circ \mathbf{X}$$\mathcal D_p(\mathbf X) = \mathbf M \circ \mathbf X$ 为 dropout 算子，其中 $M_{i,j}\sim Bern(p)$$M_{i,j}\sim Bern(p)$ 为独立同分布（ iid ）的伯努利随机变量，$\circ$$\circ$ 是逐元素的乘积。

   记 ${\mathbb{E}}_{\mathbf{M}}[\cdot ]$$\mathbb E_\mathbf M[\cdot]$ 为针对 dropout 的期望。

2. 引入 dropout 之后，即使在 GCN 中采用 exact 算法，hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 也是随机变量，其随机性来源于 dropout 。

   此时节点的邻域均值 hidden feature ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 也是一个随机变量，我们希望设计它的一个计算代价较低的估计量，从而使得二者具有相同的分布。但是这种估计量非常难以设计，因此我们设计了一个估计量 ${\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}$$\mathbf{\vec n}_{CVD,v}^{(l)}$ ，使得它和 ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 具有相同的均值和方差。即：

   $$\begin{array}{c}{\mathbb{E}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}\right]={\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_v^{(l)}\right]\\ {\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}\right]={\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_v^{(l)}\right]\end{array}$$

3. 在 dropout 场景下， $\mathrm{\Delta }{\overrightarrow{\mathbf{h}}}_u^{(l)}={\overrightarrow{\mathbf{h}}}_u^{(l)}-{\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\Delta \mathbf{\vec h}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \bar{\mathbf{\vec h}}_u^{(l)}$ 不再很小，甚至是当 ${\overline{\overrightarrow{\mathbf{h}}}}_u^{(l)}$$\bar{\mathbf{\vec h}}_u^{(l)}$ 和 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h} _u^{(l)}$ 具有相同分布的时候。为此，我们设计了另一种随机逼近算法，称作 dropout 控制变量（ control variate for dropout: CVD ）。

   我们的方法基于权重缩放（ weight scaling ）技术来近似计算均值 ${\overrightarrow{\mu }}_v^{(l)}={\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{h}}}_v^{(l)}\right]$$\vec\mu_v^{(l)} = \mathbb E_\mathbf M\left[\mathbf{\vec h}_v^{(l)}\right]$ 。即在 dropout 模型中，我们可以运行没有 dropout 的模型的copy，从而获得均值 ${\overrightarrow{\mu }}_v^{(l)}$$\vec\mu_v^{(l)}$ ，如下图 (d) 所示。

   

4. 我们通过 ${\overrightarrow{\mu }}_u^{(l)}$$\vec\mu_u^{(l)}$ 及其历史均值 ${\overline{\overrightarrow{\mu }}}_u^{(l)}$$\bar{\vec\mu}_u^{(l)}$ 来设计 CVD 估计量。

   我们将 ${\overrightarrow{\mathbf{n}}}_v^{(l)}$$\mathbf{\vec n}_v^{(l)}$ 重写为：

   $${\overrightarrow{\mathbf{n}}}_v^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overrightarrow{\mathbf{h}}}_u^{(l)}=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}({\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}+\mathrm{\Delta }{\overrightarrow{\mu }}_u^{(l)}+{\overline{\overrightarrow{\mu }}}_u^{(l)})$$

   其中：

   • $\mathrm{\Delta }{\overrightarrow{\mu }}_u^{(l)}={\overrightarrow{\mu }}_u^{(l)}-{\overline{\overrightarrow{\mu }}}_u^{(l)}$$\Delta \vec{\mu}_u^{(l)} = \vec\mu_u^{(l)} - \bar{\vec\mu}_u^{(l)}$ 为 ${\overrightarrow{\mu }}_u^{(l)}$$\vec\mu_u^{(l)}$ 及其历史均值 ${\overline{\overrightarrow{\mu }}}_u^{(l)}$$\bar{\vec\mu}_u^{(l)}$ 之间的差距。因此，可以将 ${\overrightarrow{\mu }}_u^{(l)}$$\vec\mu_u^{(l)}$ 视为 CV 估计量中的 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ 。

   • ${\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}={\overrightarrow{\mathbf{h}}}_u^{(l)}-{\overrightarrow{\mu }}_u^{(l)}$$\mathbf{\mathring{\vec h}}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \vec\mu_u^{(l)}$ 为 ${\overrightarrow{\mathbf{h}}}_u^{(l)}$$\mathbf{\vec h}_u^{(l)}$ （带 dropout ）和 ${\overrightarrow{\mu }}_u^{(l)}$$\vec\mu_u^{(l)}$ （不带 dropout ）之间的差距。

   因此定义：

   $${\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}=\sqrt{\frac{|{\mathcal{N}}_v|}{D^{(l)}}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}{\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}+\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}\mathrm{\Delta }{\overrightarrow{\mu }}_u^{(l)}+\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mu }}}_u^{(l)}$$

   则有： ${\overrightarrow{\mathbf{n}}}_v^{(l)}\simeq {\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}$$\mathbf{\vec n}_v^{(l)}\simeq \mathbf{\vec n}_{CVD,v}^{(l)}$ 。

   第一项考虑 dropout current value 和 no-dropout current value 之间的 gap，使用 $\sqrt{\cdot }$$\sqrt{\cdot}$ 是为了计算方差的方便。第二项考虑 no-dropout current value 和 no-dropout avg value 之间的 gap。第三项就是 no-dropout avg value 本身。

   考虑第一项对于 dropout 具有零均值，即 ${\mathbb{E}}_{\mathbf{M}}\left[{\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}\right]=0$$\mathbb E_\mathbf M \left[\mathbf{\mathring{\vec h}}_u^{(l)}\right] = 0$ ，因此有：

   $${\mathbb{E}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}\right]=0+{\mathbb{E}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_{CV,v}^{(l)}\right]={\mathbb{E}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_v^{(l)}\right]$$

   第一个等式成立是因为当移除 dropout 时， CVD 估计量就退化为 CV 估计量。

   因此，CVD 估计量是无偏的。下面我们即将看到，如果 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 之间不相关，则 CVD 估计量具有良好的方差。

5. 假设节点的hidden feature 之间不相关，即 $\mathrm{\forall }{v}_1\ne v_2,{\text{Cov}}_{\mathbf{M}}[{\overrightarrow{\mathbf{h}}}_{v_1}^{(l)},{\overrightarrow{\mathbf{h}}}_{v_2}^{(l)}]=0$$\forall v_1\ne v_2, \text{Cov}_\mathbf M\left[ \mathbf{\vec h}_{v_1}^{(l)}, \mathbf{\vec h}_{v_2}^{(l)}\right] = 0$ ，则我们得到两个结论：

   • 假设 ${\hat{\mathcal{N}}}_v^{(l)}$$\hat{\mathcal N}^{(l)}_v$ 通过从 ${\mathcal{N}}_v$$\mathcal N_v$ 进行无放回采样 $D^{(l)}$$D^{(l)}$ 个样本得到， $x_1,\cdots ,x_{|\mathcal{V}|}$$x_1,\cdots,x_{|\mathcal V|}$ 为一维随机变量，且满足：

     $$\begin{array}{c}\mathrm{\forall }v,\mathbb{E}[x_v]=0\\ \mathrm{\forall }{v}_1\ne v_2,\text{Cov}[x_{v_1},x_{v_2}]=0\end{array}$$

     则有：

     $${\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\text{Var}}_{\mathbf{X}}\left[\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{x}_u\right]=\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\mathcal{N}}_v^{(l)}}\text{Var}[x_u]$$

   • 令 $X$$X$ 和 $Y$$Y$ 为两个随机变量，并且 $f(X,Y)$$f(X,Y)$ 和 $g(Y)$$g(Y)$ 为两个函数。如果 ${\mathbb{E}}_X[f(X,Y)]=0$$\mathbb E_{X}[f(X,Y)] = 0$ ，则有：

     $${\text{Var}}_{X,Y}[f(X,Y)+g(Y)]={\text{Var}}_{X,Y}f(X,Y)+{\text{Var}}_{Y}g(Y)$$

   这些结论的证明参考原始论文的附录。

   通过上述结论，我们有：

   $$\begin{array}{c}{\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_{CVD,v}^{(l)}\right]={\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}{\text{Var}}_{\mathbf{M}}\left[\sqrt{\frac{|{\mathcal{N}}_v|}{D^{(l)}}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}{\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}\right]\\ +{\text{Var}}_{{\hat{\mathcal{N}}}_v^{(l)}}[\frac{|{\mathcal{N}}_v|}{D^{(l)}}\sum _{u\in {\hat{\mathcal{N}}}_v^{(l)}}{P}_{v,u}\mathrm{\Delta }{\overrightarrow{\mu }}_u^{(l)}+\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}{\overline{\overrightarrow{\mu }}}_u^{(l)}]\end{array}$$

   我们将第一项视为从 dropout 中引入的方差 （variance from dropout: VD），第二项视为从邻域采样中引入的方差 （variance from neighbor sampling: VNS）。理想情况下，VD 应该等于 ${\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_v^{(l)}\right]$$\text{Var}_{\mathbf M}\left[\mathbf{\vec n}_v^{(l)}\right]$ 、VNS 应该等于零。

   和前述相同的分析，我们可以通过将 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 替换为 ${\overrightarrow{\mu }}_v^{(l)}$$\vec\mu_v^{(l)}$ 来分析 VNS 。令 ：

   $$\begin{array}{c}{\overrightarrow{\mathbf{s}}}_u^{(l)}={\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{h}}}_v^{(l)}\right]={\text{Var}}_{\mathbf{M}}\left[{\stackrel{\mathbf{˚}}{\overrightarrow{\mathbf{h}}}}_u^{(l)}\right]\\ {\overrightarrow{\xi }}_v^{(l)}={\text{Var}}_{\mathbf{M}}\left[{\overrightarrow{\mathbf{n}}}_v^{(l)}\right]=\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}^2{\overrightarrow{\mathbf{s}}}_u^{(l)}\end{array}$$

   根据这里的第一个结论，CVD 的 VD 部分为：$\sum _{u\in {\mathcal{N}}_v}{P}_{v,u}^2{\overrightarrow{\mathbf{s}}}_u^{(l)}={\overrightarrow{\xi }}_v^{(l)}$$\sum_{u\in \mathcal N_v} P_{v,u}^2 \mathbf{\vec s}_u^{(l)} = {\vec \xi}_v^{(l)}$ ，刚好就是 exact 估计量的 VD 部分。

6. 我们总结出所有这些估计量及其方差，推导过程参考原始论文。

   • exact ： VNS 部分为零， VD 部分为 ${\overrightarrow{\xi }}_v^{(l)}$${\vec \xi}_v^{(l)}$ 。

   • NS 估计量：VNS 部分为 $\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}{(P_{v,u_1}{\overrightarrow{\mu }}_{v_1}^{(l)}-P_{v,u_2}{\overrightarrow{\mu }}_{v_2}^{(l)})}^2$$\frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\vec\mu_{v_1}^{(l)} - P_{v,u_2}\vec\mu_{v_2}^{(l)}\right)^2$ ， VD 部分为 $\frac{|{\mathcal{N}}_v|}{D^{(l)}}{\overrightarrow{\xi }}_v^{(l)}$$\frac{|\mathcal N_v|}{D^{(l)}} {\vec \xi}_v^{(l)}$ 。

   • CV 估计量：VNS 部分 $\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}{(P_{v,u_1}\mathrm{\Delta }{\overrightarrow{\mu }}_{v_1}^{(l)}-P_{v,u_2}\mathrm{\Delta }{\overrightarrow{\mu }}_{v_2}^{(l)})}^2$$\frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\Delta\vec\mu_{v_1}^{(l)} - P_{v,u_2}\Delta\vec\mu_{v_2}^{(l)}\right)^2$ ，VD 部分$(3+\frac{|{\mathcal{N}}_v|}{D^{(l)}}){\overrightarrow{\xi }}_v^{(l)}$$\left(3+\frac{|\mathcal N_v|}{D^{(l)}} \right) {\vec \xi}_v^{(l)}$ 。

   • CVD 估计量：VNS 部分 $\frac{C_v^{(l)}}{2D^{(l)}}\sum _{u_1\in {\mathcal{N}}_v}\sum _{u_2\in {\mathcal{N}}_v}{(P_{v,u_1}\mathrm{\Delta }{\overrightarrow{\mu }}_{v_1}^{(l)}-P_{v,u_2}\mathrm{\Delta }{\overrightarrow{\mu }}_{v_2}^{(l)})}^2$$\frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\Delta\vec\mu_{v_1}^{(l)} - P_{v,u_2}\Delta\vec\mu_{v_2}^{(l)}\right)^2$ ， VD 部分为 ${\overrightarrow{\xi }}_v^{(l)}$${\vec \xi}_v^{(l)}$ 。

   CV/CVD 的 VNS 取决于 $\mathrm{\Delta }{\overrightarrow{\mu }}_v$$\Delta\vec\mu_{v}$ ，随着训练的进行 $\mathrm{\Delta }{\overrightarrow{\mu }}_v$$\Delta\vec\mu_{v}$ 收敛到零；NS 的 VNS 取决于非零的 ${\overrightarrow{\mu }}_v$$\vec\mu_{v}$ 。